#pragma once
#include<iostream>
using namespace std;

bool IsPrime(int n)
{
	for (int i = 2; i <=sqrt(n); i++)
		if (n % i == 0)
			return false;

	return true;
}
int FindMaxPrime(int n)
{
	int maxPrime = 1;
	for (int i = 2; i < n; i++)
	{
		if (IsPrime(i)) 
			maxPrime = max(maxPrime, i);
	}
	return maxPrime;
}

#include<unordered_map>
vector<int> FindSameNum(vector<int>& arr)
{
	unordered_map<int, int> um;//元素-出现次数
	vector<int> ans;

	for (auto& x : arr)
		um[x]++;
	
	for (auto& kv : um)
	{
		if (kv.second == 2)
			ans.push_back(kv.first);
	}
	
	return ans;
}

vector<string> SplitStrToArr(string str)
{
	vector<string> arr;
	int start = 0, end = 0;//标志当前的字符串，以空格为单位进行切分
	while (end < str.size())
	{
		end = start;
		while (end < str.size() && str[end] != '&')
			end++;
		//跳出循环时：end指向第一个&

		end++; //end指向第二个&

		//此时[start,end-2]就是对应的字符，共end-2-start+1个字符
		arr.push_back(str.substr(start, end - start - 1));
		//跳到下一个字符串的开头
		start = end + 1;
	}
	return arr;
}

string ArrToString(vector<string>& str)
{
	string sep  = "&&";
	string ans;
	int n = str.size();
	for (int i = 0; i <n - 1; i++)
	{
		ans += str[i];
		ans += sep;
	}
	ans += str[n-1];
	return ans;
}

int main()
{
	vector<string> ans = SplitStrToArr("ab&&2&&gello&&world");
	for (auto& x : ans)
		cout << x << endl;
	return 0;
}



//当前来到letter的index位置的字符，当前形成的字符串为str，答案保存在ans当中
void process(string& letter,int index,string str,vector<string>& ans)
{
	if (index == letter.size() && str.size() == 0) //空串不要
		return;
	if (index == letter.size())
	{
		ans.push_back(str);
		return;
	}

	//要当前位置的字符 || 不要当前位置的字符
	process(letter, index + 1, str + letter[index], ans);
	process(letter, index + 1, str, ans);
}
vector<string> GroupLetter()
{
	vector<string> ans;
	string tmp;
	string letter = "ab";
	process(letter,0, tmp, ans);
	return ans;
}

//n个人(编号1~n)，从编号为1的开始报数到m，报数到m的出去，然后下一个人重新从1开始报数，求最后留下的人
int josephus(int n, int m)
{
	list<int> people;
	for (int i = 1; i <= n; i++)
		people.push_back(i);//人员编号1~n

	auto iter = people.begin();//从哪个人开始报数
	while (people.size() > 1) //当只有一个人的时候就结束循环，他就是留下的人
	{
		for (int count = 1; count < m; count++) //从1开始报数到m，只需要走m-1步
		{
			iter++;
			//如果到达end()位置，需要重新回到开头！（循环队列）
			if (iter == people.end())
				iter = people.begin();
		}

		//此时iter就是报数为m的人，需要移除
		iter = people.erase(iter);

		//erase:返回删除位置的下一个位置的迭代器，所以此时iter可能为end() ！！需要重新回到开头
		if (iter == people.end())
			iter = people.begin();

	}
	//最后剩余的唯一的一个人就是留下的人
	return people.front();
}
int Process(int n, int m)
{
	int ans = 0;  // 记录最后一个幸存者的编号

	for (int i = 2; i <= n; ++i) 
	{
		ans = (ans + m) % i;
	}

	// 因为编号从1开始，所以要+1返回才是最终答案
	return ans + 1;
}

//
//int main()
//{
//	vector<string> ans = GroupLetter();
//	for (auto& x : ans)
//		cout << x << endl;
//	cout << ans.size();
//	return 0;
//}